package com.lw.leetcode.tree.c;

import com.lw.leetcode.tree.TreeNode;

/**
 * 1373. 二叉搜索子树的最大键值和
 *
 * @Author liw
 * @Date 2021/8/22 17:19
 * @Version 1.0
 */
public class MaxSumBST {

    // 最小值， 最大值， 是否是二叉树， 和， 子节点的最大和
    public static void main(String[] args) {
        MaxSumBST test = new MaxSumBST();

        TreeNode instance11 = TreeNode.getInstance11();
        int i = test.maxSumBST(instance11);


        System.out.println(i);
    }

    public int maxSumBST(TreeNode root) {
        int[] ints = find(root);
        return ints[4];
    }

    public int[] find(TreeNode node) {
        int val = node.val;
        if (node.left == null && node.right == null) {
            return new int[]{val, val, 1, val, val > 0 ? val : 0};
        }
        int[] al = null;
        int[] ar = null;
        if (node.left != null) {
            al = find(node.left);
        }
        if (node.right != null) {
            ar = find(node.right);
        }
        if (ar == null) {
            if (al[2] == 0) {
                return al;
            }
            if (al[1] >= val) {
                al[2] = 0;
                return al;
            }
            al[1] = val;
            al[3] += val;
            al[4] = Math.max(al[3], al[4]);
            return al;
        }
        if (al == null) {
            if (ar[2] == 0) {
                return ar;
            }
            if (ar[0] <= val) {
                ar[2] = 0;
                return ar;
            }
            ar[0] = val;
            ar[3] += val;
            ar[4] = Math.max(ar[3], ar[4]);
            return ar;
        }
        if (al[2] == 0 || ar[2] == 0 || al[1] >= val || ar[0] <= val) {
            al[2] = 0;
            al[4] = Math.max(al[4], ar[4]);
            return al;
        }
        al[1] = ar[1];
        al[3] = al[3] + ar[3] + val;
        al[4] = Math.max(al[3], Math.max(al[4], ar[4]));
        return al;
    }
}
